Longest Substring Without Repeating Characters

Description

Given a string, find the length of the longest substring without repeating characters.

Input: “abcabcbb”
Output: 3

Input: “bbbbb”
Output: 1

Input: “pwwkew”
Output: 3

####Solution

借鉴了别人的思路，让我觉得很巧妙的一点是，忽略子字符串的具体内容，利用数组记录字符的位置，只比较当前字符的位置是否出现在最左端的右边，代码如下：

int lengthOfLongestSubstring(string s)
{
	int m[256];//字符共有256个，ascii码为i的字符最近位置为m[i]
	for (int i = 0; i < 256; i++)
		m[i] = -1;
	int res = 0;//最大的长度
	int left = 0;//左端点的编号
	for (int rg = 0; rg < s.size(); ++rg)
	{
		if (res == 0 || m[s[rg]] < left)
		{//还未开始移动，或在当前子字符串中无字母s[rg]
			res = res > rg - left + 1 ? res : rg - left + 1;
			m[s[rg]] = rg;
		}
		else
		{//当前子字符串中存在字母s[rg]
			left = m[s[rg]] + 1;
			m[s[rg]] = rg;
		}
	}
	return res;
}

对特殊的字符串进行测试：

string a = "abcabcbb";
	string b = "bbbbb";
	string c = "pwwkew";
	string d = "122*hfks2ilnuibin";
	string e = "au";
	cout << lengthOfLongestSubstring(a) << " " << lengthOfLongestSubstring(b) << " " 
		<< lengthOfLongestSubstring(c) <<" "<< lengthOfLongestSubstring(d) << " " << lengthOfLongestSubstring(e) << endl;

输出结果为：3 1 3 10 2

在提交时出现的一种错误情况，即对于字符串“au”输出长度为1，经过检查，是因为最开始在初始化m时，将m的元素全部设为了0，上面的代码中已进行了修正。